62. Unique Paths

发表于 | 分类于 | 浏览 次

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

img
Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

1
2
3
4
5
6
7
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

1
2
Input: m = 7, n = 3
Output: 28

本题很简单,只需要在暴力搜索的基础上加上计划化搜索就行.这里不再赘述思路,详情请见代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m <= 0 || n <= 0){
            return 0;
        }
        vector<vector<int>> res(m, vector<int>(n, -1));
        return dfs(m, n, 0, 0, res);
    }
    int dfs(int m, int n, int posx, int posy, vector<vector<int>> & res){
        if(res[posx][posy] != -1){
            return res[posx][posy];
        }
        if(posx == m - 1 && posy == n-1){
            res[posx][posy] = 1;
            return 1;
        }
        int s1, s2;
        if(posx +1 < m){
            s1 = res[posx+1][posy] == -1 ? dfs(m, n, posx + 1, posy, res) : res[posx+1][posy];
        }else{
            s1 = 0;
        }
        if(posy + 1 < n){
            s2 = res[posx][posy+1] == -1 ? dfs(m, n, posx, posy +1, res) :  res[posx][posy+1];            
        }else{
            s2 = 0;
        }
        res[posx][posy] = s1 + s2;
        return s1 + s2;
    }
};